package leetCode.solution;

import java.util.ArrayList;
import java.util.List;

/**
 * 给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target
 * 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。 candidates 中的 同一个 数字可以 无限制重复被选取
 * 。如果至少一个数字的被选数量不同，则两种组合是不同的。 对于给定的输入，保证和为 target 的不同组合数少于 150 个。
 * 
 * @author jerry
 * @ClassName: Solution39
 * @Description:
 * @date 2022年11月11日 下午4:11:13
 */
class Solution39 {

	public static void main(String[] args) {
		System.out.println(new Solution39().combinationSum(new int[] { 2, 3, 6,7 }, 7));
	}

	List<List<Integer>> result = new ArrayList<List<Integer>>();

	public List<List<Integer>> combinationSum(int[] candidates, int target) {
		process(candidates, target, 0, new ArrayList<Integer>());
		return result;
	}

	private void process(int[] candidates, int rest, int index, List<Integer> outPut) {
		if (rest < 0) {
			return;
		}
		if (rest == 0) {
			result.add(new ArrayList<Integer>(outPut));
			return;
		}

		if(index<candidates.length) {
			process(candidates, rest, index + 1, outPut);
			outPut.add(candidates[index]);
			process(candidates, rest-candidates[index], index, outPut);
			outPut.remove(outPut.size() - 1);
		}
	}
	
}